package com.leetcode;

import com.leetcode.common.ListNode;

import static com.leetcode.util.LinkedListUtil.createList;
import static com.leetcode.util.LinkedListUtil.printList;

/**
 * 147. 对链表进行插入排序
 */
public class Solution147 {

    /**
     * 加速版
     *
     * @param head
     * @return
     */
    public ListNode insertionSortList(ListNode head) {
        ListNode dummyHead = new ListNode(Integer.MIN_VALUE, head);
        ListNode cur = dummyHead.next;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = null;

            ListNode p = dummyHead;
            while (p.next != null && p.next.val <= cur.val) {
                p = p.next;
            }
            ListNode last = p.next;
            p.next = cur;
            cur.next = last;

            cur = next;
        }
        return dummyHead.next;
    }

    public ListNode insertionSortList1(ListNode head) {
        ListNode dummyHead = new ListNode(Integer.MIN_VALUE, head);
        ListNode cur = dummyHead.next;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = null;
            insert(dummyHead, cur);
            cur = next;
        }
        return dummyHead.next;
    }

    private void insert(ListNode head, ListNode next) {
        while (head.next != null && head.next.val <= next.val) {
            head = head.next;
        }
        ListNode last = head.next;
        head.next = next;
        next.next = last;
    }

    public static void main(String[] args) {
        ListNode head = createList(new int[]{-1, -1, 5, 3, 4, 0});
        printList(head);

        ListNode newHead = new Solution147().insertionSortList(head);
        printList(newHead);
    }

}
